#include <cstdio>
#include <cstring>
#include <climits>

int prime[1001];
int prime_size;
bool prime_mark[1001];

void init_prime(){
    for (int i = 0; i <= 1000; i++)
        prime_mark[i] = true;
    prime_size = 0;

    for (int i = 2; i <= 1000; i++){
        if (prime_mark[i] == false)
            continue;
        prime[prime_size++] = i;
        for (int j = i*i; j <= 1000; j += i) // start from i*i not 2*i
            prime_mark[j] = false;
    }
}

int prime_pow_n[1001];
int prime_pow_a[1001];

int main(int argc, char const *argv[]){
    int n, a;
    init_prime();
    while (scanf("%d%d", &n, &a) != EOF){
        for (int i = 0; i < prime_size; i++)
            prime_pow_n[i] = prime_pow_a[i] = 0;
        for (int i = 0; i < prime_size; i++){
            int temp_num = n;
            while (temp_num){
                prime_pow_n[i] += temp_num/prime[i];
                temp_num = temp_num / prime[i];
            }
        }
        int result = INT_MAX;
        for (int i = 0; i < prime_size; i++){
            while (a % prime[i] == 0){
                prime_pow_a[i]++;
                a /= prime[i];
            }
            if (prime_pow_a[i] == 0)
                continue;
            if (prime_pow_n[i] / prime_pow_a[i] < result)
                result = prime_pow_n[i] / prime_pow_a[i];
        }
        printf("%d\n", result);
    }
    return 0;
}
